package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.LinkedProblem;

/**
 * https://leetcode.com/problems/linked-list-cycle-ii/discuss/44793/O(n)-solution-by-using-two-pointers-without-change-anything
 * */
public class LC142_1 implements LinkedProblem {
    ListNode detectCycle(ListNode head) {
        if (head == null || head.next == null) return null;

        ListNode firstp = head;
        ListNode secondp = head;
        boolean isCycle = false;

        while (firstp != null && secondp != null) {
            firstp = firstp.next;
            if (secondp.next == null) return null;
            secondp = secondp.next.next;
            if (firstp == secondp) {
                isCycle = true;
                break;
            }
        }

        if (!isCycle) return null;
        firstp = head;
        while (firstp != secondp) {
            firstp = firstp.next;
            secondp = secondp.next;
        }

        return firstp;
    }

    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n5;
        System.out.println(new LC142_1().detectCycle(n1).val);
    }
}
